home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / minimax.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  4.6 KB  |  147 lines
  1. /*-----------------------------------------------------------------------------
  2. MINIMAX.C
  3.  
  4. This file contains the tree searching minimax algorithms.
  5.  
  6. Revision History
  7. ----------------
  8. Jon Ward     2 Jan 1989    Initial Revision
  9. Jon Ward     7 Jan 1989    Added last_max_score var for statistical stuff.
  10. -----------------------------------------------------------------------------*/
  11.  
  12. #include <stdio.h>
  13. #include <limits.h>
  14.  
  15. #include "othello.h"
  16.  
  17.  
  18. /*-----------------------------------------------------------------------------
  19.               Global Variable Declarations
  20. -----------------------------------------------------------------------------*/
  21. int last_max_score;
  22.  
  23. /*-----------------------------------------------------------------------------
  24.                Local Function Prototypes
  25. -----------------------------------------------------------------------------*/
  26. STATIC int mm_max (
  27.    key_type parent,        /* limb whose children will be maxd */
  28.    int depth,            /* number of levels to minimax */
  29.    key_type *best);        /* pointer to best move */
  30.  
  31. STATIC int mm_min (
  32.    key_type parent,        /* limb whose children will be mind */
  33.    int depth,            /* number of levels to minimax */
  34.    key_type *worst);        /* pointer to worst move */
  35.  
  36.  
  37. /*-----------------------------------------------------------------------------
  38. STATIC int mm_max (
  39.    key_type parent,
  40.    int depth,
  41.    key_type *best);
  42.  
  43. This function will find the maximal board score depth levels below the parent.
  44. The value returned is the maximal score.
  45. -----------------------------------------------------------------------------*/
  46.  
  47. STATIC int mm_max (
  48.    key_type parent,        /* limb whose children will be maxd */
  49.    int depth,            /* number of levels to minimax */
  50.    key_type *best)        /* pointer to best move */
  51. {
  52. register int max;        /* value for the maximal limb */
  53. int score;            /* score for the current limb */
  54. limb_type far *l;        /* pointer to the limb for the current limb */
  55. register key_type limb;        /* key for the current limb */
  56.  
  57. max = INT_MIN;            /* minimum int value */
  58.  
  59. limb = (db_retrieve_limb (parent))->bc.child_key;
  60.  
  61. for (; limb != NO_KEY; limb = l->sibling_key)
  62.   {
  63.   l = db_retrieve_limb (limb);
  64.  
  65.   score = (depth) ? mm_min (limb, depth - 1, NULL) : l->score;
  66.  
  67.   if (score > max)
  68.     {
  69.     max = score;
  70.     if (best)
  71.       *best = limb;
  72.     }
  73.   }
  74.  
  75. return (max);
  76. }
  77.  
  78.  
  79. /*-----------------------------------------------------------------------------
  80. STATIC int mm_min (
  81.    key_type parent,
  82.    int depth,
  83.    key_type *worst);
  84.  
  85. This function will find the minimal board score depth levels below the parent.
  86. The value returned is the minimal score.
  87. -----------------------------------------------------------------------------*/
  88.  
  89. STATIC int mm_min (
  90.    key_type parent,        /* limb whose children will be mind */
  91.    int depth,            /* number of levels to minimax */
  92.    key_type *worst)        /* pointer to worst move */
  93. {
  94. register int min;        /* value for the minimal limb */
  95. int score;            /* score for the current limb */
  96. limb_type far *l;        /* pointer to the limb for the current limb */
  97. register key_type limb;        /* key for the current limb */
  98.  
  99. min = INT_MAX;            /* maximum int value */
  100.  
  101. limb = (db_retrieve_limb (parent))->bc.child_key;
  102.  
  103. for (; limb != NO_KEY; limb = l->sibling_key)
  104.   {
  105.   l = db_retrieve_limb (limb);
  106.  
  107.   score = (depth) ? mm_max (limb, depth - 1, NULL) : l->score;
  108.  
  109.   if (score < min)
  110.     {
  111.     min = score;
  112.     if (worst)
  113.       *worst = limb;
  114.     }
  115.   }
  116.  
  117. return (min);
  118. }
  119.  
  120.  
  121. /*-----------------------------------------------------------------------------
  122. key_type find_best_move (
  123.    key_type root,
  124.    int depth);
  125.  
  126. This function returns the key of the maximal move for the root referenced by
  127. the root argument. Note that the root key is the key for the currently
  128. displayed board and that its children are the moves that will finally be
  129. considered. The depth argument is the number of levels of children that exist
  130. below the root.  For example, depth = 1 means that there is only one level
  131. built below the root.
  132. -----------------------------------------------------------------------------*/
  133.  
  134. key_type find_best_move (
  135.    key_type root,        /* key to root of tree */
  136.    int depth)            /* levels below root to look */
  137. {
  138. key_type best_move;
  139.  
  140. last_max_score = mm_max (root, depth - 1, &best_move);    /* do the minimax */
  141. return (best_move);            /* return the limb key of the best move */
  142. }
  143.  
  144. /*-----------------------------------------------------------------------------
  145. -----------------------------------------------------------------------------*/
  146.  
  147.